package com.zm.demo.core.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Collectors;

/**
 * @author zoum
 * @create 2020/1/14 10:07
 */
public class ReorganizeString {

    public static String reorganizeString(String S) {

        if (S == null || S.length() == 0){
            return "";
        }
        int length = S.length();
        int[]chars = new int[26];
        Map<Character, Integer> map = new HashMap<>();
        char[]dp = new char[S.length()];

        int max = -1;
        for (int i = 0; i < S.length(); i++) {
            chars[S.charAt(i) -'a']++;
            max = Math.max(chars[S.charAt(i) -'a'], max);
        }

        if (max > (length+1)/2){
            return "";
        }

        int index0 = 0;
        int index1 = 1;
        for (int i = 0; i < 26; i++) {
            if (chars[i] < (length/2+1)){
                while (chars[i] > 0 && index1 < length){
                    dp[index1] = (char)('a'+i);
                    index1+=2;
                    chars[i]--;
                }
            }

            while (chars[i] > 0 && index0 < length){
                dp[index0] = (char)('a'+i);
                index0+=2;
                chars[i]--;
            }

        }
        return new String(dp);

    }

    public static void main(String[] args){
        reorganizeString("aan");
    }
}


